package pers.sloera.leetcode.editor.cn;

/**
 * 质数排列
 *
 * @author sloera
 * @date 2022-06-30 21:53:17
 */
class PrimeArrangements {
    public static void main(String[] args) {
        Solution solution = new PrimeArrangements().new Solution();
        // System.out.println(solution.numPrimeArrangements(5));
        System.out.println(solution.numPrimeArrangements(100));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // int MOD = (int) (Math.pow(10, 9) + 7);
        int MOD = (int) (1e9 + 7);

        public int numPrimeArrangements(int n) {
            int primeNumber = findPrimeNumber(n);
            return (int) ((factorial(primeNumber) * factorial(n - primeNumber)) % MOD);
        }

        // 计算n的阶乘
        private long factorial(int n) {
            int res = 1;
            // a = b * c + d
            // a * x = b * c * x + d * x
            // a * x % c = d * x % c
            // 注意边界溢出
            for (long i = 1L; i <= n; i++) {
                res = (int) ((res * i) % MOD);
            }
            return res;
        }

        // 寻找[1,n]有多少个质数
        private int findPrimeNumber(int n) {
            int result = 0;
            boolean isPrime;
            for (int out = 2; out <= n; out++) {
                if (out == 2 || out == 3) {
                    result++;
                    continue;
                }
                isPrime = true;
                for (int i = 2; i <= Math.ceil(Math.sqrt(out)); i++) {
                    if (out % i == 0) {
                        isPrime = false;
                        break;
                    }
                }
                if (isPrime) {
                    result++;
                }
            }
            return result;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}
